package com.dhj.top100;

import java.util.*;

public class GroupAnagrams {

    public static void main(String[] args) {
        System.out.println(groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
    }


    public static List<List<String>> groupAnagrams2(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for(String str: strs){
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            List<String> value = map.getOrDefault(key, new ArrayList<>());
            value.add(str);
            map.put(key, value);
        }
        return new ArrayList<>(map.values());

    }



    public static List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> result = new ArrayList<>();

        for(int i = 0; i < strs.length; i++){
            List<String> subList = new ArrayList<>();
            for (int j = i+1; j < strs.length; j++) {
                if(isAnagram(strs[i], strs[j])){
                    subList.add(strs[j]);
                    strs[j] = null;
                }
            }
            if(strs[i] != null){
                subList.add(strs[i]);
            }
           if(!subList.isEmpty()){
               result.add(subList);
           }
        }
        return result;
    }

    public static boolean isAnagram(String s1, String s2) {
        if(s1 == null || s2 == null){
            return false;
        }
        if (s1.length() != s2.length()) {
            return false;
        }
        String[] subChar = s1.split("");
        String[] subChar2 = s2.split("");
        for (String ele : subChar){
            int i =0;
            for (; i < subChar2.length; i++) {
                if(subChar2[i] == null){
                    continue;
                }
                if(ele.equals(subChar2[i])){
                    subChar2[i] = null;
                    break;
                }
            }
            if(i == subChar2.length){
                return false;
            }
        }
        return true;
    }

}
